package com.lcy.struct.bTreePlus.disk.core.engine;

import com.lcy.struct.bTreePlus.disk.core.BPlusTree;
import com.lcy.struct.bTreePlus.disk.core.BPlusTreeFactory;
import com.lcy.struct.bTreePlus.disk.index.BTreeIndex;
import com.lcy.struct.bTreePlus.entity.BplusTreeTransactionInfo;
import com.lcy.struct.bTreePlus.property.BPlusFileInfo;

import java.util.HashMap;
import java.util.Map;

/**
 * @author lucongyang
 * @date Created in  10:46
 * @description
 */
public class BPlusTreeDelEngine {
    private Map<Long, BPlusTree> needSerializeMap = new HashMap<>();

    public static BPlusTreeDelEngine getInstance() {
        return BPlusTreeDelEngineHandler.SINGLETON;
    }

    public boolean delData(Comparable... index) {
        BPlusTree leaf = BPlusTreeFactory.findLeafOnDisk(index);
        if (leaf == null) {
            return false;
        }
        Integer i = BPlusTreeFactory.findDataInLeaf(leaf, index);
        if (i == null) {
            return false;
        }
        // 先删了再说
        BTreeIndex toDelIndexInLeaf = leaf.getIndexList().get(i);
        leaf.removeItem(i);
        addNeedSerialize(leaf);
        BPlusFileInfo.countMinusOne();
        // 获取b+tree阶数
        Integer rank = BPlusFileInfo.getRankBPlusTree();
        int needNum = rank / 2;

        // 如果是祖先节点直接过
        if (leaf.isRoot()) {
            return true;
        }

        BPlusTree parent = BPlusTreeFactory.getTree(leaf.getParentPosition());
        // 第一种情况，如果节点数据量大于rank/2，直接删
        if (leaf.getIndexList().size() >= needNum) {
            disposeWhenSufficient(leaf, parent, toDelIndexInLeaf, index);
        }
        // 第二大情况，如果节点数据量不大于rank/2
        else {
            disposeWhenInsufficient(leaf, needNum, toDelIndexInLeaf, rank);
        }

        return true;
    }

    private void disposeWhenInsufficient(BPlusTree leaf, int needNum, BTreeIndex toDelIndexInLeaf, int rank) {
        // 1.如果是祖先节点
        if (leaf.isRoot()) {
            return;
        }
        // 2. 如果不是祖先节点，那只能向兄弟节点求助
        // 找出大于rank/2的兄弟节点
        BPlusTree brother = null;
        boolean left = false;
        BPlusTree leftBrother = leaf.getLeftPosition() != null ? BPlusTreeFactory.getTree(leaf.getLeftPosition()) : null;
        BPlusTree rightBrother = null;
        // 看看同一父节点下的左兄弟能不能借
        if (leftBrother != null && leftBrother.getDataList().size() > needNum && leftBrother.getParentPosition().equals(leaf.getParentPosition())) {
            brother = leftBrother;
            left = true;
        }
        // 再看看同一父节点下的右的
        if (brother == null) {
            rightBrother = leaf.getRightPosition() != null ? BPlusTreeFactory.getTree(leaf.getRightPosition()) : null;
            if (rightBrother != null && rightBrother.getDataList().size() > needNum && rightBrother.getParentPosition().equals(leaf.getParentPosition())) {
                brother = rightBrother;
            }
        }
        // 2.1 如果大于rank/2的兄弟存在
        BPlusTree leafParent = BPlusTreeFactory.getTree(leaf.getParentPosition());
        if (brother != null) {
            BTreeIndex borrow = null;
            boolean toDelIndexFirstInLeaf = toDelIndexInLeaf.compare(leaf.getIndexList().get(0)) < 0;
            // 2.1.1 借一个节点
            if (left) {
                // 2.1.1.1如果是向左节点借的
                borrow = brother.getIndexList().get(brother.getIndexList().size() - 1);
                leaf.getIndexList().add(0, borrow);
                leaf.getDataList().add(0, brother.getDataList().get(brother.getDataList().size() - 1));
                brother.removeItem(brother.getIndexList().size() - 1);
                // 肯定涉及父节点索引
                Integer index = leafParent.indexOfIndex(toDelIndexInLeaf);
                index = index != null ? index : leafParent.indexOfIndex(leaf.getIndexList().get(1));
                leafParent.getIndexList().set(index, leaf.getIndexList().get(0));
                addNeedSerialize(leafParent, leaf, brother);
            } else {
                // 2.1.1.2如果是向右节点借的
                borrow = brother.getIndexList().get(0);
                leaf.getIndexList().add(borrow);
                leaf.getDataList().add(brother.getDataList().get(0));
                brother.removeItem(0);
                Integer indexOfBrotherIndexInBrotherParent = leafParent.indexOfIndex(borrow);
                // 将现在右节点的第一个更新到原父节点的位置上
                leafParent.getIndexList().set(indexOfBrotherIndexInBrotherParent, brother.getIndexList().get(0));
                addNeedSerialize(leafParent, leaf, brother);
                // 如果被删节点涉及父节点索引
                Integer index = leafParent.indexOfIndex(toDelIndexInLeaf);
                if (index != null) {
                    leafParent.getIndexList().set(index, leaf.getIndexList().get(0));
                }
            }
            // 如果被删索引涉及上级节点：如果该节点是父中的第一个节点，且被删索引是原索引中的第一个
            if (leafParent.indexOfIndex(leaf.getIndexList().get(0)) == null && toDelIndexFirstInLeaf) {
                // 如果被删节点涉及上面节点的索引,则替换成leaf的第一个索引
                BPlusTree indexInParent = leafParent;
                Integer toDelIndexInLeafParent = null;
                while (true) {
                    toDelIndexInLeafParent = indexInParent.indexOfIndex(toDelIndexInLeaf);
                    if (toDelIndexInLeafParent != null) {
                        break;
                    }
                    if (indexInParent.isRoot()) {
                        break;
                    }
                    indexInParent = BPlusTreeFactory.getTree(indexInParent.getParentPosition());
                }
                if (toDelIndexInLeafParent != null) {
                    indexInParent.getIndexList().set(toDelIndexInLeafParent, leaf.getIndexList().get(0));
                    addNeedSerialize(indexInParent);
                }
            }
        }
        // 2.2. 如果大于rank/2的兄弟不存在,那就合并,默认向左合并
        else {
            BPlusTree bindBrother = null;
            // 如果左兄弟存在且在一个父节点上
            if (leftBrother != null && leftBrother.getParentPosition().equals(leaf.getParentPosition())) {
                // 2.2.1 如果左节点存在,就合并到左节点
                bindBrother = leftBrother;
                bindBrother.getIndexList().addAll(leaf.getIndexList());
                bindBrother.getDataList().addAll(leaf.getDataList());
                // 需考虑左右节点问题
                bindBrother.setRightPosition(leaf.getRightPosition());
                if (leaf.getRightPosition() != null) {
                    BPlusTree leafRight = BPlusTreeFactory.getTree(leaf.getRightPosition());
                    leafRight.setLeftPosition(bindBrother.getPosition());
                    addNeedSerialize(leafRight);
                }
                // 肯定涉及父索引的删除
                Integer toDelIndexInParent = leafParent.indexOfIndex(leaf.getIndexList().get(0));
                if (toDelIndexInParent == null) {
                    toDelIndexInParent = leafParent.indexOfIndex(toDelIndexInLeaf);
                }
                leafParent.removeItem(toDelIndexInParent);
                leafParent.getChildrenPosition().remove(toDelIndexInParent + 1);
                addNeedSerialize(bindBrother, leafParent);
            } else {
                // 2.2.2 如果右节点存在，就合并到右节点,对于叶子节点来说，此情况只可能是该leaf节点是该父亲节点下的第一个叶子节点
                bindBrother = BPlusTreeFactory.getTree(leaf.getRightPosition());
                bindBrother.getIndexList().addAll(0, leaf.getIndexList());
                bindBrother.getDataList().addAll(0, leaf.getDataList());
                bindBrother.setLeftPosition(leaf.getLeftPosition());
                // 如果左节点存在，修改左右索引
                if (leaf.getLeftPosition() != null) {
                    BPlusTree leafLeft = BPlusTreeFactory.getTree(leaf.getLeftPosition());
                    leafLeft.setRightPosition(bindBrother.getPosition());
                    addNeedSerialize(leafLeft);
                }
                addNeedSerialize(bindBrother);
                // 修改父索引，删除兄弟的
                leafParent.getIndexList().remove(0);
                leafParent.getChildrenPosition().remove(0);
                addNeedSerialize(leafParent);
                // 3. 如果被删节点涉及上级节点：如果该节点是父中的第一个节点，且被删节点是原父节点中的第一个
                if (toDelIndexInLeaf.compare(leaf.getIndexList().get(0)) < 0) {
                    // 如果被删节点涉及上面节点的索引,则替换成leaf的第一个索引
                    BPlusTree indexInParent = leafParent;
                    Integer toDelIndexInLeafParent = null;
                    while (true) {
                        toDelIndexInLeafParent = indexInParent.indexOfIndex(toDelIndexInLeaf);
                        if (toDelIndexInLeafParent != null) {
                            break;
                        }
                        if (indexInParent.isRoot()) {
                            break;
                        }
                        indexInParent = BPlusTreeFactory.getTree(indexInParent.getParentPosition());
                    }
                    if (toDelIndexInLeafParent != null) {
                        indexInParent.getIndexList().set(toDelIndexInLeafParent, bindBrother.getIndexList().get(0));
                        addNeedSerialize(indexInParent);
                    }
                }
            }
            removeNeedSerialize(leaf);

            // 看看父节点是不是空了
            if (leafParent.getIndexList().size() == 0) {
                // 这种情况只可能是祖先节点
                if (!leafParent.isRoot()) {
                    String msg = String.format("不是祖先节点，索引项数=%s,B+tree阶数=%s", leafParent.getIndexList().size(), rank);
                    throw new RuntimeException(msg);
                }
                // 更换祖先节点为当前节点
                BPlusFileInfo.setRootPosition(bindBrother.getPosition());
//                BPlusFileInfo.saveRootPosition();
                bindBrother.setParentPosition(null);
                addNeedSerialize(bindBrother);
                return;
            }
            // 2.2.3.3 如果合并后的节点的父节点项目数小于rank/2
            disposeNotLeafWhenInSufficient(leafParent, rank);
        }
    }

    private void disposeNotLeafWhenInSufficient(BPlusTree bPlusTree, int rank) {
        // 根节点不管
        if (bPlusTree.isRoot()) {
            return;
        }
        // 枝繁叶茂的不管
        int standardIndexSize = ((rank - 1) / 2);
        if (bPlusTree.getIndexList().size() >= standardIndexSize) {
            return;
        }
        BPlusTree parent = BPlusTreeFactory.getTree(bPlusTree.getParentPosition());
        int bPlusTreeIndexInParentChildren = parent.getChildrenPosition().indexOf(bPlusTree.getPosition());
        BPlusTree borrowBrother = null;
        // 1. 向兄弟节点借
        // 1.1 先看看左兄弟，此判断已确保在一个父节点下
        if (bPlusTreeIndexInParentChildren > 0) {
            BPlusTree leftBrother = BPlusTreeFactory.getTree(parent.getChildrenPosition().get(bPlusTreeIndexInParentChildren - 1));
            // 如果左兄弟富裕，就向左兄弟借一个项
            if (leftBrother.getIndexList().size() > standardIndexSize) {
                borrowBrother = leftBrother;
                // 找出节点的第一个左叶子节点
                BPlusTree firstLeftLeafFromBplusTree = findPointLeaf(bPlusTree, true);
                // 借操作
                bPlusTree.getIndexList().add(0, firstLeftLeafFromBplusTree.getIndexList().get(0));
                bPlusTree.getChildrenPosition().add(0, borrowBrother.getChildrenPosition().get(borrowBrother.getChildrenPosition().size() - 1));
                // 4. 修改共同父节点索引信息
                // 4.1 第一个左叶子节点在公共祖先上的位置
                Integer index = parent.indexOfIndex(firstLeftLeafFromBplusTree.getIndexList().get(0));
                // 4.2 更新
                BPlusTree firstLeftLeafFromBplusTreeAfterBorrow = findPointLeaf(bPlusTree, true);
                parent.getIndexList().set(index, firstLeftLeafFromBplusTreeAfterBorrow.getIndexList().get(0));
                // 被合并的项重新认父
                BPlusTree borrowBrotherLastChild = BPlusTreeFactory.getTree(borrowBrother.getChildrenPosition()
                        .get(borrowBrother.getChildrenPosition().size() - 1));
                borrowBrotherLastChild.setParentPosition(bPlusTree.getPosition());
                // 兄弟节点删除
                borrowBrother.removeItem(borrowBrother.getIndexList().size() - 1);
                borrowBrother.getChildrenPosition().remove(borrowBrother.getChildrenPosition().size() - 1);

                addNeedSerialize(bPlusTree, borrowBrother, parent, borrowBrotherLastChild);
            }
        }
        // 1.2 左兄弟不行看右兄弟可不可以借
        if (borrowBrother == null) {
            Long rightBrotherPosition = bPlusTreeIndexInParentChildren + 1 < parent.getChildrenPosition().size() ?
                    parent.getChildrenPosition().get(bPlusTreeIndexInParentChildren + 1) : null;
            BPlusTree rightBrother = rightBrotherPosition != null ? BPlusTreeFactory.getTree(rightBrotherPosition) : null;
            if (!bPlusTree.getPosition().equals(rightBrotherPosition) && rightBrother != null &&
                    rightBrother.getIndexList().size() > standardIndexSize) {
                borrowBrother = rightBrother;
                // 找出兄弟节点的第一个左叶子节点
                BPlusTree firstLeftLeafFromBorrwoBrother = findPointLeaf(borrowBrother, true);
                // 借操作
                BPlusTree bindBrotherFirstChild = BPlusTreeFactory.getTree(borrowBrother.getChildrenPosition().get(0));
                bPlusTree.getIndexList().add(firstLeftLeafFromBorrwoBrother.getIndexList().get(0));
                bPlusTree.getChildrenPosition().add(borrowBrother.getChildrenPosition().get(0));
                // 被合并的项重新认父
                bindBrotherFirstChild.setParentPosition(bPlusTree.getPosition());
                // 兄弟节点删除
                borrowBrother.removeItem(0);
                borrowBrother.getChildrenPosition().remove(0);
                // 4. 修改共同父节点索引信息
                // 4.1 第一个左叶子节点在公共祖先上的位置
                Integer index = parent.indexOfIndex(firstLeftLeafFromBorrwoBrother.getIndexList().get(0));
                // 4.2 更新
                BPlusTree firstLeftLeafFromBorrowBrotherAfterBorrow = findPointLeaf(borrowBrother, true);
                parent.getIndexList().set(index, firstLeftLeafFromBorrowBrotherAfterBorrow.getIndexList().get(0));

                addNeedSerialize(bindBrotherFirstChild, borrowBrother, parent, bPlusTree);
            }
        }
        if (borrowBrother != null) {
            // 说明借到了
            return;
        }
        // 2. 麻烦的是没借到，只能合并
        /**
         * 1. 假设rank为奇数
         * 则次情况下standardIndexSize=(rank-1)/2,兄弟节点个数为(rank-1)/2,加上自己（缺了一项）为(ran-1)/2-1,和为rank-2,
         * 加上他们的父节点的一个项合并上来，总数为rank-1，刚好饱和，满足rank阶B+tree性质
         * 2. 假设rank为偶数
         * 则此情况下standardIndexSize=rank/2-1,兄弟节点的个数为rank/2-1,加上自己（缺了一项）为(rank/2-2),和为rank-3
         * 加上他们的父节点的一个项合并上来，总数为rank-2，虽然饱和，满足rank阶B+tree性质
         */
        BPlusTree bindBrother = null;
        // 如果存在左兄弟，默认向左合并，此判断已确保在一个父节点下
        if (bPlusTreeIndexInParentChildren > 0) {
            // 找出左兄弟节点
            BPlusTree leftBrother = BPlusTreeFactory.getTree(parent.getChildrenPosition().get(bPlusTreeIndexInParentChildren - 1));
            bindBrother = leftBrother;
            // 找出自己在父索引里的位置
            int middleIndex = bPlusTree.getIndexList().get(0).findIndex(parent.getIndexList()) - 1;
            // 找出需要下降的索引项
            BTreeIndex downIndex = parent.getIndexList().get(middleIndex);
            // 父节点删除该项
            parent.getIndexList().remove(middleIndex);
            // 父节点的孩子中删除当前节点
            parent.getChildrenPosition().remove(bPlusTreeIndexInParentChildren);
            // 当前节点首部加上父级下级的索引项
            bPlusTree.getIndexList().add(0, downIndex);
            // 与左兄弟合并,索引，孩子
            leftBrother.getIndexList().addAll(bPlusTree.getIndexList());
            leftBrother.getChildrenPosition().addAll(bPlusTree.getChildrenPosition());
            // 将当前节点下的孩子重新认父为左兄弟节点
            for (Long childPosition : bPlusTree.getChildrenPosition()) {
                BPlusTree childTree = BPlusTreeFactory.getTree(childPosition);
                childTree.setParentPosition(leftBrother.getPosition());
                addNeedSerialize(childTree);
            }
            addNeedSerialize(leftBrother, parent);
            removeNeedSerialize(bPlusTree);
        }
        // 如果不存在左兄弟，就向右合并
        else {
            // 找出左兄弟节点
            BPlusTree rightBrother = BPlusTreeFactory.getTree(parent.getChildrenPosition().get(bPlusTreeIndexInParentChildren + 1));
            bindBrother = rightBrother;
            // 找出自己在父索引里的位置
            int middleIndex = rightBrother.getIndexList().get(0).findIndex(parent.getIndexList()) - 1;
            // 找出需要下降的索引项
            BTreeIndex downIndex = parent.getIndexList().get(middleIndex);
            // 父节点删除该项
            parent.getIndexList().remove(middleIndex);
            // 父节点的孩子中删除当前节点
            parent.getChildrenPosition().remove(bPlusTreeIndexInParentChildren);
            // 当前节点首部加上父级下级的索引项
            bPlusTree.getIndexList().add(downIndex);
            // 与右兄弟合并,索引，孩子
            rightBrother.getIndexList().addAll(0, bPlusTree.getIndexList());
            rightBrother.getChildrenPosition().addAll(0, bPlusTree.getChildrenPosition());
            // 将当前节点下的孩子重新认父为右兄弟节点
            for (Long childPosition : bPlusTree.getChildrenPosition()) {
                BPlusTree childTree = BPlusTreeFactory.getTree(childPosition);
                childTree.setParentPosition(rightBrother.getPosition());
                addNeedSerialize(childTree);
            }
            addNeedSerialize(rightBrother, parent);
            removeNeedSerialize(bPlusTree);
        }
        // 看看父节点是不是空了
        if (parent.getIndexList().size() == 0) {
            // 这种情况只可能是祖先节点
            if (!parent.isRoot()) {
                String msg = String.format("不是祖先节点，索引项数=%s,B+tree阶数=%s,合法最新索引数=%s", parent.getIndexList().size(), rank, standardIndexSize);
                throw new RuntimeException(msg);
            }
            // 更换祖先节点为当前节点
            BPlusFileInfo.setRootPosition(bindBrother.getPosition());
//            BPlusFileInfo.saveRootPosition();
            bindBrother.setParentPosition(null);
            addNeedSerialize(bindBrother);
            return;
        }
        // 如果父节点索引数小于标准
        if (parent.getIndexList().size() < standardIndexSize) {
            disposeNotLeafWhenInSufficient(parent, rank);
        }
    }

    private void disposeWhenSufficient(BPlusTree leaf, BPlusTree leafParent, BTreeIndex toDelIndexInLeaf, Comparable... index) {
        boolean containsIndex = leafParent.containsIndex(index);
        if (!containsIndex) {
            // 如果不是索引节点
            // 直接删除
        } else {
            // 如果是索引节点
            Integer indexInParent = leafParent.indexOfIndex(index);
            leafParent.getIndexList().set(indexInParent, leaf.getIndexList().get(0));
            addNeedSerialize(leaf, leafParent);
        }
        // 如果被删索引涉及上级节点：如果该节点是父中的第一个节点，且被删索引是原索引中的第一个
        if (leafParent.indexOfIndex(leaf.getIndexList().get(0)) == null && toDelIndexInLeaf.compare(leaf.getIndexList().get(0)) < 0) {
            // 如果被删节点涉及上面节点的索引,则替换成leaf的第一个索引
            BPlusTree indexInParent = leafParent;
            Integer toDelIndexInLeafParent = null;
            while (true) {
                toDelIndexInLeafParent = indexInParent.indexOfIndex(toDelIndexInLeaf);
                if (toDelIndexInLeafParent != null) {
                    break;
                }
                if (indexInParent.isRoot()) {
                    break;
                }
                indexInParent = BPlusTreeFactory.getTree(indexInParent.getParentPosition());
            }
            if (toDelIndexInLeafParent != null) {
                indexInParent.getIndexList().set(toDelIndexInLeafParent, leaf.getIndexList().get(0));
                addNeedSerialize(indexInParent);
            }
        }
    }

    /**
     * 只能被消费一次
     *
     * @return 事务中需要持久化数据
     */
    public BplusTreeTransactionInfo getSerializeCacheNeed() {
        // todo 加锁
        BplusTreeTransactionInfo bplusTreeTransactionInfo = new BplusTreeTransactionInfo();
        bplusTreeTransactionInfo.setCount(BPlusFileInfo.getCount());
        bplusTreeTransactionInfo.setEndPosition(BPlusFileInfo.getEndPosition());
        bplusTreeTransactionInfo.setRootPosition(BPlusFileInfo.getRootPosition());

        bplusTreeTransactionInfo.setNeedSerializeMap(this.needSerializeMap);

        this.needSerializeMap = new HashMap<>();
        return bplusTreeTransactionInfo;
    }

    private static class BPlusTreeDelEngineHandler {
        private static final BPlusTreeDelEngine SINGLETON = new BPlusTreeDelEngine();
    }

    private void addNeedSerialize(BPlusTree... bPlusTrees) {
        for (BPlusTree bPlusTree : bPlusTrees) {
            needSerializeMap.put(bPlusTree.getPosition(), bPlusTree);
            BPlusTreeFactory.addCache(bPlusTree);
        }
    }

    private void removeNeedSerialize(BPlusTree... bPlusTrees) {
        for (BPlusTree bPlusTree : bPlusTrees) {
            needSerializeMap.remove(bPlusTree.getPosition());
            BPlusTreeFactory.removeCache(bPlusTree);
        }
    }

    /**
     * 找到两个节点的根
     * 两者需要在同一层，不然报错
     */
    private BPlusTree findSimpleSenior(BPlusTree a, BPlusTree b) {
        if (a.getParentPosition().equals(b.getParentPosition())) {
            return BPlusTreeFactory.getTree(a.getParentPosition());
        }
        BPlusTree aParent = BPlusTreeFactory.getTree(a.getParentPosition());
        BPlusTree bParent = BPlusTreeFactory.getTree(b.getParentPosition());
        return findSimpleSenior(aParent, bParent);
    }

    /**
     * 找到指定非叶子节点最左或最右叶子节点
     */
    private BPlusTree findPointLeaf(BPlusTree bPlusTree, boolean left) {
        if (bPlusTree.isLeaf()) {
            return bPlusTree;
        }
        if (left) {
            BPlusTree child = BPlusTreeFactory.getTree(bPlusTree.getChildrenPosition().get(0));
            return findPointLeaf(child, true);
        } else {
            BPlusTree child = BPlusTreeFactory.getTree(bPlusTree.getChildrenPosition().get(bPlusTree.getChildrenPosition().size() - 1));
            return findPointLeaf(child, false);
        }
    }
}
